package com.itheima.leetcode.od.b.dynamicprogramming;

/**
 * <h3>构造数列（有点类似Leetcode300-最长递增子序列）</h3>
 * 小明在做构造数列的题目，题目要求数列中第一个数为n，且数列后面的每一个数字都不能大于前一个数字的一半，数列的元素都是正整数，请问在给定n的情况下，最多能构造多少合法且不同的数列？ 输入描述 输入一个n 备注 1 <= n< 10000 输出描述 输出可以构造的序列个数
 * <p>
 * 示例1：
 * <p>
 * 输入：
 * <p>
 * 7
 * <p>
 * 输出：
 * <p>
 * 6
 * <p>
 * 说明：
 * <p>
 * 可以构成 [7], [7,3],[7,2],[7,1],[7,3,1],[7,2,1]
 * <p>
 * 示例2：
 * <p>
 * 输入：
 * <p>
 * 5
 * <p>
 * 输出：
 * <p>
 * 4
 * <p>
 * 说明：
 * <p>
 * 可以构成 [5],[5,2],[5,1],[5,2,1]
 */
public class CountSequences {

    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        long result = getResult(n);
        System.out.println(result);

        scanner.close();*/

        int n = 7;

        System.out.println(getResult(n));
    }

    /**
     * 计算以n开头的合法数列个数
     * 使用动态规划自底向上计算
     * 有点分治的概念
     *
     * @param n
     * @return
     */
    private static long getResult(int n) {
        // dp[i]表示以i开头能构造的数列个数，而不是传统的i表示坐标
        long[] dp = new long[n + 1];

        // 边界条件：以1开头只能构造[1]
        dp[1] = 1;

        // 自底向上计算
        for (int i = 2; i <= n; i++) {
            // 至少可以构造[i]这一个数列
            dp[i] = 1;

            // 加上所有可能的后续数字开头的数列
            for (int j = 1; j <= i / 2; j++) {
                dp[i] += dp[j];
            }
        }

        return dp[n];
    }
}